"""
1. 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
"""


def seek_in_sorted_list(xlist, target) -> (int, bool):
    """
    给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

    :param xlist: 排序后列表
    :param target: 目标
    :return: int, bool 索引，是否已经存在
    """
    left, right = None, None
    for i, x in enumerate(xlist):
        if x == target:
            return i, True
        if x < target:
            left = i
        else:
            right = i
        if left is not None and right is not None:
            return left + 1, False


if '__main__' == __name__:

    def main():
        xlist = sorted([-5, -3, 0, 1, 2, 5, 7, 8, 9, 11, 100, 101])
        print(xlist)
        targets = [-5, -4, -3, -2, 0, 2, 6, 50]
        for x in targets:
            print(x, '->', seek_in_sorted_list(xlist, x))

    main()
